package com.leetcode.partition4;

/**
 * @author `RKC`
 * @date 2021/8/12 8:31
 */
public class LC377组合总数4 {

    public static int combinationSum4(int[] nums, int target) {
        // return dynamicProgramming(nums, target);
        return backtracking(nums, target, 0);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int target = 4;
        System.out.println(combinationSum4(nums, target));
    }

    private static int backtracking(int[] nums, int target, int sum) {
        if (sum > target) return 0;
        if (sum == target) return 1;
        int answer = 0;
        for (int i = 0; i < nums.length; i++) {
            answer += backtracking(nums, target, sum + nums[i]);
        }
        return answer;
    }
    
    private static int dynamicProgramming(int[] nums, int target) {
        //dp[i]：凑够i的dp[i]种方式
        int[] dp = new int[target + 1];
        dp[0] = 1;
        //组合问题可以不用考虑元素的顺序，例如[1, 1, 2]和[1, 2, 1]是同一个；而排列问题需要考虑元素的顺序，如[1, 1, 2]、[1, 2, 1]、[2, 1, 1]是不同的
        //如果先遍历物品后遍历容量则只会访问到[1, 1, 2]而不会有[2, 1, 1]的情况；因此该题目需要先遍历容量后遍历物品
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] > i) continue;              //背包装不下
                dp[i] = dp[i] + dp[i - nums[j]];
            }
        }
        return dp[target];
    }
}
